package com.platform.modules.alg.alglib.hdu5057;

import static java.lang.Math.sqrt;

public class Hdu5057 {

    private int maxn = 100010;
    int a[] = new int[maxn];
    int belong[] = new int[maxn];
    int L[] = new int[maxn];
    int R[] = new int[maxn];
    // block[i][j][k] 表示第 i 块中第 j 位上是 k 的数有多少个
    int block[][][] = new int[400][12][12];
    int n;
    int m;

    int ten[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

    void build() {
        int t = (int) sqrt(n);
        int num = n / t;
        if (n % t != 0) num++;
        for (int i = 1; i <= num; i++) {
            // 每块的左右位置，从 1 开始
            L[i] = (i - 1) * t + 1;
            R[i] = i * t;
        }
        R[num] = n;
        for (int i = 1; i <= n; i++)
            belong[i] = (i - 1) / t + 1; // 所属块，从 1 开始
        for (int i = 1; i <= n; i++) {
            int temp = a[i];
            for (int j = 1; j <= 10; j++) { // 位数最多有 10 位 1<=D<=10
                block[belong[i]][j][temp % 10]++; // 块，位，位上的数
                temp /= 10;
            }
        }
    }

    int query(int l, int r, int d, int p) {
        int ans = 0;
        if (belong[l] == belong[r]) { // 属于同一块
            for (int i = l; i <= r; i++) // 暴力统计
                if ((a[i] / ten[d]) % 10 == p)
                    ans++;
            return ans;
        }
        for (int i = belong[l] + 1; i < belong[r]; i++) // 累加中间块
            ans += block[i][d][p];
        for (int i = l; i <= R[belong[l]]; i++) { // 左端暴力累加
            if ((a[i] / ten[d]) % 10 == p)
                ans++;
        }
        for (int i = L[belong[r]]; i <= r; i++) { // 右端暴力累加
            if ((a[i] / ten[d]) % 10 == p)
                ans++;
        }
        return ans;
    }

    void update(int x, int y) {
        for (int i = 1; i <= 10; i++) { // 原来的统计数减少
            block[belong[x]][i][a[x] % 10]--;
            a[x] /= 10;
        }
        a[x] = y;
        for (int i = 1; i <= 10; i++) { // 新的统计数增加
            block[belong[x]][i][y % 10]++;
            y /= 10;
        }
    }

    public String output = "";

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);

        String[] key = line[1].split(" ");

        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(key[i - 1]);
        }
        build(); // 划分块
        int j = 0;
        while (m-- > 0) {
            String[] command = line[j + 2].split(" ");
            j++;

            if (command[0].charAt(0) == 'S') {
                int x, y;
                x = Integer.parseInt(command[1]);
                y = Integer.parseInt(command[2]);
                update(x, y);
            } else {
                int l, r, d, p;
                l = Integer.parseInt(command[1]);
                r = Integer.parseInt(command[2]);
                d = Integer.parseInt(command[3]);
                p = Integer.parseInt(command[4]);
                output += query(l, r, d, p) + "\n";
            }
        }
        return output;
    }
}
